home *** CD-ROM | disk | FTP | other *** search
/ Inter.Net 55-1 / Inter.Net 55-1.iso / CBuilder / Setup / BCB / data.z / tree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1998-02-09  |  29.0 KB  |  907 lines
  1. #ifndef __STD_TREE__
  2. #define __STD_TREE__
  3. #pragma option push -b -a4 -Vx- -Ve- -w-inl -w-aus -w-sig
  4.  
  5. /***************************************************************************
  6.  *
  7.  * tree - Declarations for the Standard Library tree classes
  8.  *
  9.  * $Id: tree,v 1.68 1996/09/30 02:29:07 smithey Exp $
  10.  *
  11.  ***************************************************************************
  12.  *
  13.  * Copyright (c) 1994
  14.  * Hewlett-Packard Company
  15.  *
  16.  * Permission to use, copy, modify, distribute and sell this software
  17.  * and its documentation for any purpose is hereby granted without fee,
  18.  * provided that the above copyright notice appear in all copies and
  19.  * that both that copyright notice and this permission notice appear
  20.  * in supporting documentation.  Hewlett-Packard Company makes no
  21.  * representations about the suitability of this software for any
  22.  * purpose.  It is provided "as is" without express or implied warranty.
  23.  *
  24.  *
  25.  ***************************************************************************
  26.  *
  27.  * (c) Copyright 1994, 1995 Rogue Wave Software, Inc.
  28.  * ALL RIGHTS RESERVED *
  29.  * The software and information contained herein are proprietary to, and
  30.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  31.  * intends to preserve as trade secrets such software and information.
  32.  * This software is furnished pursuant to a written license agreement and
  33.  * may be used, copied, transmitted, and stored only in accordance with
  34.  * the terms of such license and with the inclusion of the above copyright
  35.  * notice.  This software and information or any other copies thereof may
  36.  * not be provided or otherwise made available to any other person.
  37.  *
  38.  * Notwithstanding any other lease or license that may pertain to, or
  39.  * accompany the delivery of, this computer software and information, the
  40.  * rights of the Government regarding its use, reproduction and disclosure
  41.  * are as set forth in Section 52.227-19 of the FARS Computer
  42.  * Software-Restricted Rights clause.
  43.  * 
  44.  * Use, duplication, or disclosure by the Government is subject to
  45.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  46.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  47.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  48.  * P.O. Box 2328, Corvallis, Oregon 97339.
  49.  *
  50.  * This computer software and information is distributed with "restricted
  51.  * rights."  Use, duplication or disclosure is subject to restrictions as
  52.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  53.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  54.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  55.  * then the "Alternate III" clause applies.
  56.  *
  57.  **************************************************************************/
  58.  
  59. /*
  60. **
  61. ** Red-black tree class, designed for use in implementing STL
  62. ** associative containers (set, multiset, map, and multimap). The
  63. ** insertion and deletion algorithms are based on those in Cormen,
  64. ** Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
  65. ** except that:
  66. ** 
  67. ** (1) the header cell is maintained with links not only to the root
  68. ** but also to the leftmost node of the tree, to enable constant time
  69. ** begin(), and to the rightmost node of the tree, to enable linear time
  70. ** performance when used with the generic set algorithms (set_union,
  71. ** etc.);
  72. ** 
  73. ** (2) when a node being deleted has two children its successor node is
  74. ** relinked into its place, rather than copied, so that the only
  75. ** iterators invalidated are those referring to the deleted node.
  76. ** 
  77. */
  78.  
  79. #include <stdcomp.h>
  80.  
  81. #ifndef _RWSTD_HEADER_REQUIRES_HPP
  82. #include <algorithm>
  83. #include <iterator>
  84. #else
  85. #include <algorithm.hpp>
  86. #include <iterator.hpp>
  87. #endif
  88.  
  89. #ifdef _RWSTD_MULTI_THREAD
  90. #include <rw/stdmutex.h>
  91. #endif
  92.  
  93. #ifndef _RWSTD_NO_NAMESPACE
  94. namespace __rwstd {
  95. using namespace std;
  96. #endif
  97.  
  98. #ifndef rb_tree 
  99. #define rb_tree rb_tree
  100. #endif
  101.  
  102. //
  103. // And a mutex to ensure NIL gets set properly for each type of tree.
  104. //
  105. #ifdef _RWSTD_MULTI_THREAD
  106. extern _RWSTDMutex _RWSTDExport __stl_tree_mutex;
  107. #endif
  108.  
  109. template <class Key, class Value, class KeyOfValue, 
  110.           class Compare, class Allocator>
  111. class rb_tree
  112. {
  113.   protected:
  114.  
  115.     enum color_type { rb_red, rb_black };
  116.  
  117.     struct rb_tree_node;
  118.     friend struct rb_tree_node;
  119.  
  120. #ifdef _RWSTD_ALLOCATOR
  121.     typedef _TYPENAME Allocator::rebind<void>::other::pointer  void_pointer;
  122.     typedef _TYPENAME Allocator::rebind<Value>::other  value_alloc_type;
  123.     typedef _TYPENAME Allocator::rebind<Key>::other    key_alloc_type;
  124.     typedef _TYPENAME Allocator::rebind<rb_tree_node>::other node_alloc_type;
  125. #else
  126.     typedef allocator_interface<Allocator,Value>      value_alloc_type;
  127.     typedef allocator_interface<Allocator,Key>        key_alloc_type;
  128.     typedef allocator_interface<Allocator,rb_tree_node> node_alloc_type;
  129.     typedef value_alloc_type::void_pointer void_pointer;
  130. #endif
  131.  
  132.     struct rb_tree_node
  133.     {
  134. #if defined(__WIN32__) || defined(__WIN16__)
  135.     bool         isNIL;
  136. #endif
  137.         ~rb_tree_node() { ; }
  138.         color_type   color_field; 
  139.         void_pointer parent_link;
  140.         void_pointer left_link;
  141.         void_pointer right_link;
  142.         Value        value_field;
  143.     };
  144.  
  145.     typedef _TYPENAME value_alloc_type::pointer          pointer;
  146.     typedef _TYPENAME value_alloc_type::const_pointer    const_pointer;
  147.     typedef _TYPENAME key_alloc_type::const_reference    const_key_reference;
  148.  
  149. #ifdef __WIN16__
  150.     static rb_tree_node theNilNode;
  151. #endif
  152.  
  153.   public:
  154.  
  155.     typedef Key                                        key_type;
  156.     typedef Value                                      value_type;
  157.     typedef Allocator                                  allocator_type;
  158.  
  159. #ifndef _RWSTD_NO_COMPLICATED_TYPEDEF
  160.     typedef _TYPENAME _RWSTD_ALLOC_SIZE_TYPE             size_type;
  161.     typedef _TYPENAME _RWSTD_ALLOC_DIFF_TYPE             difference_type;
  162.     typedef _TYPENAME value_alloc_type::reference       reference;
  163.     typedef _TYPENAME value_alloc_type::const_reference const_reference;
  164. #else
  165.     typedef size_t             size_type;
  166.     typedef ptrdiff_t          difference_type;
  167.     typedef Value&                 reference;
  168.     typedef const Value&           const_reference;
  169. #endif  //_RWSTD_NO_COMPLICATED_TYPEDEF
  170.  
  171.     typedef _TYPENAME node_alloc_type::pointer          link_type;
  172.  
  173.   protected:
  174.     allocator_type the_allocator;
  175.     size_type buffer_size;
  176.  
  177.     struct rb_tree_node_buffer;
  178.     friend struct rb_tree_node_buffer;
  179.  
  180.     struct rb_tree_node_buffer
  181.     {
  182.         ~rb_tree_node_buffer() { ; }
  183.         void_pointer next_buffer;
  184.         size_type size;
  185.         link_type buffer;
  186.     };
  187.  
  188.     static bool isNil(const link_type& l) 
  189.     { 
  190. #if defined(__WIN32__) || defined(__WIN16__)
  191.       if ((*l).isNIL) 
  192.         return true; 
  193.       return false; 
  194. #else
  195.       return l == NIL;
  196. #endif
  197.     }
  198.  
  199.   public:
  200.  
  201. #ifdef _RWSTD_ALLOCATOR
  202.     typedef _TYPENAME allocator_type::rebind<rb_tree_node_buffer>::other buffer_alloc_type;
  203. #else
  204.     typedef allocator_interface<Allocator,rb_tree_node_buffer> buffer_alloc_type;
  205. #endif
  206.     typedef buffer_alloc_type::pointer buffer_pointer;
  207.     
  208.   protected:
  209.     buffer_pointer                 buffer_list;
  210.     link_type                      free_list;
  211.     link_type                      next_avail;
  212.     link_type                      last;
  213.    
  214.     void add_new_buffer ()
  215.     {
  216.         buffer_pointer tmp = buffer_alloc_type(the_allocator).allocate(_RWSTD_STATIC_CAST(size_type,1),buffer_list);
  217.         tmp->buffer        = node_alloc_type(the_allocator).allocate(buffer_size,last);
  218.         tmp->next_buffer   = buffer_list;
  219.         tmp->size          = buffer_size;
  220.         buffer_list        = tmp;
  221.         next_avail         = buffer_list->buffer;
  222.         last               = next_avail + buffer_size;
  223.     }
  224.     void deallocate_buffers ();
  225.  
  226.     // 
  227.     // Return a node from the free list or new storage
  228.     //
  229.     link_type get_link()
  230.     {
  231.         link_type tmp = free_list;
  232.         link_type tmp2 = free_list ? 
  233.       (free_list = _RWSTD_STATIC_CAST(link_type,(free_list->right_link)), tmp) 
  234.       : (next_avail == last ? (add_new_buffer(), next_avail++) 
  235.          : next_avail++);
  236.       #if defined(__WIN32__) || defined(__WIN16__)
  237.         tmp2->isNIL = false;
  238.       #endif
  239.         return tmp2;
  240.     }
  241.  
  242.     //
  243.     // Return a node from the free list or new storage with
  244.     // the Value v constructed on it.  Every call to get_node
  245.     // must eventually be followed by a call to put_node.
  246.     //
  247.     link_type get_node (const Value& v)
  248.     {
  249.         link_type tmp2 = get_link();
  250.         value_alloc_type va(the_allocator);
  251.         va.construct(va.address(value(tmp2)),v);
  252.         return tmp2;
  253.     }
  254.     link_type get_node ()
  255.     {
  256.         return get_link();
  257.     }
  258.  
  259.     // 
  260.     // Return a node to the free list and destroy the value in it.
  261.     //
  262.     void put_node (link_type p, bool do_destroy = true) 
  263.     { 
  264.       p->right_link = free_list; 
  265.       if (do_destroy)      
  266.       {
  267.         value_alloc_type va(the_allocator);
  268.         va.destroy(va.address(value(p)));  
  269.       }
  270.       free_list = p; 
  271.     }
  272.  
  273.   protected:
  274.  
  275.     link_type  header;  
  276.     link_type& root      ()       { return parent(header); }
  277.     link_type& root      () const { return parent(header); }
  278.     link_type& leftmost  ()       { return left(header);   }
  279.     link_type& leftmost  () const { return left(header);   }
  280.     link_type& rightmost ()       { return right(header);  }
  281.     link_type& rightmost () const { return right(header);  }
  282.  
  283.     size_type  node_count;    // Keeps track of size of tree.
  284.     bool       insert_always; // Controls whether an element already in the
  285.                               // tree is inserted again.
  286.     Compare   key_compare;
  287.  
  288.     static link_type NIL;
  289. #ifndef __WIN16__
  290.     static size_type number_of_trees;
  291. #endif
  292.  
  293.     static link_type& left (link_type x)
  294.     {
  295.         return _RWSTD_REINTERPRET_CAST(link_type&,((*x).left_link));
  296.     }
  297.     static link_type& right (link_type x)
  298.     {
  299.         return _RWSTD_REINTERPRET_CAST(link_type&,((*x).right_link));
  300.     }
  301.     static link_type& parent (link_type x)
  302.     {
  303.         return _RWSTD_REINTERPRET_CAST(link_type&,((*x).parent_link));
  304.     }
  305.     static reference value (link_type x) { return (*x).value_field; }
  306.     static const_key_reference key (link_type x)
  307.     {
  308.         return KeyOfValue()(value(x));
  309.     }
  310.     static color_type& color (link_type x)
  311.     {
  312.         return _RWSTD_STATIC_CAST(color_type&,(*x).color_field);
  313.     }
  314.     static link_type minimum (link_type x)
  315.     {
  316.         while (!isNil(left(x))) x = left(x);
  317.         return x;
  318.     }
  319.     static link_type maximum (link_type x)
  320.     {
  321.         while (!isNil(right(x))) x = right(x);
  322.         return x;
  323.     }
  324.  
  325.   public:
  326.  
  327.     class  iterator;
  328.     friend class iterator;
  329.     class  const_iterator;
  330.     friend class const_iterator;
  331.  
  332.     class iterator : public bidirectional_iterator<Value, difference_type>
  333.     {
  334.         friend class rb_tree<Key, Value, KeyOfValue, Compare, Allocator>;
  335.         friend class const_iterator;
  336.  
  337.       protected:
  338.  
  339.         link_type node;
  340.         iterator (link_type x) : node(x) {}        
  341.  
  342.       public:
  343.  
  344.         iterator () {}
  345.         bool operator== (const iterator& y) const { return node == y.node; }
  346.         bool operator!= (const iterator& y) const { return node != y.node; }
  347.         reference operator* () const { return value(node); }
  348.         iterator& operator++ ()
  349.         {
  350.             if (!isNil(right(node)))
  351.             {
  352.                 node = right(node);
  353.                 while (!isNil(left(node))) node = left(node);
  354.             }
  355.             else
  356.             {
  357.                 link_type y = parent(node);
  358.                 while (node == right(y))
  359.                 {
  360.                     node = y; y = parent(y);
  361.                 }
  362.                 if (right(node) != y) // Necessary because of rightmost.
  363.                     node = y;
  364.             }
  365.             return *this;
  366.         }
  367.         iterator operator++ (int)
  368.         {
  369.             iterator tmp = *this; ++*this; return tmp;
  370.         }
  371.         iterator& operator-- ()
  372.         {
  373.             if (color(node) == rb_red && parent(parent(node)) == node)  
  374.                 //
  375.                 // Check for header.
  376.                 //
  377.                 node = right(node);   // Return rightmost.
  378.             else if (!isNil(left(node)))
  379.             {
  380.                 link_type y = left(node);
  381.                 while (!isNil(right(y))) y = right(y);
  382.                 node = y;
  383.             }
  384.             else
  385.             {
  386.                 link_type y = parent(node);
  387.                 while (node == left(y))
  388.                 {
  389.                     node = y; y = parent(y);
  390.                 }
  391.                 node = y;
  392.             }
  393.             return *this;
  394.         }
  395.         iterator operator-- (int)
  396.         {
  397.             iterator tmp = *this; --*this; return tmp;
  398.         }
  399.  
  400.     };  // End of definition of iterator.
  401.  
  402.     class const_iterator
  403.         : public bidirectional_iterator<Value,difference_type>
  404.     {
  405.         friend class rb_tree<Key, Value, KeyOfValue, Compare, Allocator>;
  406.         friend class iterator;
  407.  
  408.       protected:
  409.  
  410.         link_type node;
  411.         const_iterator (link_type x) : node(x) {}
  412.  
  413.       public:
  414.  
  415.         const_iterator () {}
  416.         const_iterator (const iterator& x) : node(x.node) {}
  417.         bool operator== (const const_iterator& y) const
  418.         { 
  419.             return node == y.node; 
  420.         }
  421.         bool operator!= (const const_iterator& y) const
  422.         { 
  423.             return node != y.node; 
  424.         }
  425.         const_reference operator* () const { return value(node); }
  426.         const_iterator& operator++ ()
  427.         {
  428.             if (!isNil(right(node)))
  429.             {
  430.                 node = right(node);
  431.                 while (!isNil(left(node))) node = left(node);
  432.             }
  433.             else
  434.             {
  435.                 link_type y = parent(node);
  436.                 while (node == right(y))
  437.                 {
  438.                     node = y; y = parent(y);
  439.                 }
  440.                 if (right(node) != y) // Necessary because of rightmost.
  441.                     node = y;
  442.             }
  443.             return *this;
  444.         }
  445.         const_iterator operator++ (int)
  446.         {
  447.             const_iterator tmp = *this; ++*this; return tmp;
  448.         }
  449.         const_iterator& operator-- ()
  450.         {
  451.             if (color(node) == rb_red && parent(parent(node)) == node)  
  452.                 //
  453.                 // Check for header.
  454.                 //
  455.                 node = right(node);   // return rightmost
  456.             else if (!isNil(left(node)))
  457.             {
  458.                 link_type y = left(node);
  459.                 while (!isNil(right(y))) y = right(y);
  460.                 node = y;
  461.             }
  462.             else
  463.             {
  464.                 link_type y = parent(node);
  465.                 while (node == left(y))
  466.                 {
  467.                     node = y; y = parent(y);
  468.                 }
  469.                 node = y;
  470.             }
  471.             return *this;
  472.         }
  473.         const_iterator operator-- (int)
  474.         {
  475.             const_iterator tmp = *this; --*this; return tmp;
  476.         }
  477.     };  // End of definition of const_iterator.
  478.  
  479. #ifndef _RWSTD_NO_NAMESPACE
  480.     typedef ::std::reverse_bidirectional_iterator<iterator, value_type,
  481.                        reference,pointer, difference_type>
  482.             reverse_iterator; 
  483.     typedef ::std::reverse_bidirectional_iterator<const_iterator, value_type,
  484.                             const_reference, const_pointer, difference_type>
  485.             const_reverse_iterator;
  486. #else
  487.     typedef ::reverse_bidirectional_iterator<iterator, value_type,
  488.                        reference,pointer, difference_type>
  489.             reverse_iterator; 
  490.     typedef ::reverse_bidirectional_iterator<const_iterator, value_type,
  491.                             const_reference, const_pointer, difference_type>
  492.             const_reverse_iterator;
  493. #endif
  494.  
  495.   private:
  496.  
  497.     iterator  __insert (link_type x, link_type y, const value_type& v);
  498.     link_type __copy   (link_type x, link_type p);
  499.     void      __erase  (link_type x);
  500.     void init ()
  501.     {
  502.         buffer_size = 1;
  503.     buffer_list = 0;
  504.         free_list = next_avail = last = 0;
  505.  
  506.     {
  507. #ifdef _RWSTD_MULTI_THREAD
  508.         _RWSTDGuard guard(__stl_tree_mutex);
  509. #endif
  510. #ifndef __WIN16__
  511.         ++number_of_trees;
  512. #endif
  513.             if (NIL == 0)
  514.             {
  515. #ifdef __WIN16__
  516.                 NIL = &theNilNode; 
  517. #else
  518.                 NIL = node_alloc_type(the_allocator).allocate(_RWSTD_STATIC_CAST(size_type,1),last);
  519. #endif
  520.                 color(NIL)  = rb_black;
  521.                 parent(NIL) = 0;
  522.                 left(NIL)   = 0;
  523.                 right(NIL)  = 0;
  524. #if defined(__WIN32__) || defined(__WIN16__)
  525.                 (*NIL).isNIL   = true;
  526. #endif
  527.             }
  528.     }
  529.         header        = get_node();
  530.         color(header) = rb_red;  // Used to distinguish header from root
  531.                               // in iterator.operator++.
  532.         root()      = NIL;
  533.         leftmost()  = header;
  534.         rightmost() = header;
  535.         buffer_size   = 
  536.         1 >__RWSTD::__rw_allocation_size((value_type*)0,(size_type)0) ? 1 : __RWSTD::__rw_allocation_size((value_type*)0,(size_type)0);
  537. //max((size_type)1,__RWSTD::__rw_allocation_size((value_type*)0,(size_type)0));
  538.     }
  539.   public:
  540.  
  541.     rb_tree (const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare()), bool always _RWSTD_DEFAULT_ARG(true),
  542.              const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator())) 
  543.            : node_count(0), key_compare(_RWSTD_COMP), 
  544.              insert_always(always), the_allocator(alloc)
  545.     {
  546.         init();
  547.     }
  548.  
  549. #ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
  550.     rb_tree (void) 
  551.            : node_count(0), key_compare(Compare()), 
  552.              insert_always(true), the_allocator(Allocator())
  553.     {
  554.         init();
  555.     }
  556.  
  557.     rb_tree (const Compare& _RWSTD_COMP) 
  558.            : node_count(0), key_compare(_RWSTD_COMP), 
  559.              insert_always(true), the_allocator(Allocator())
  560.     {
  561.         init();
  562.     }
  563.  
  564.     rb_tree (const Compare& _RWSTD_COMP , bool always = true)
  565.            : node_count(0), key_compare(_RWSTD_COMP), 
  566.              insert_always(always), the_allocator(Allocator())
  567.     {
  568.         init();
  569.     }
  570. #endif
  571.  
  572. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  573.     template<class InputIterator>
  574.     rb_tree (InputIterator first, InputIterator last, 
  575.              const Compare& comp = Compare(), bool always = true,
  576.              const Allocator& alloc = Allocator())
  577.           : node_count(0), key_compare(comp), 
  578.             insert_always(always), the_allocator(alloc)
  579.     { 
  580.         init(); 
  581.         insert(first, last);
  582.     }
  583. #else
  584.     rb_tree (const value_type* first, const value_type* last, 
  585.              const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare()), bool always _RWSTD_DEFAULT_ARG(true),
  586.              const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
  587.           : node_count(0), key_compare(_RWSTD_COMP), 
  588.             insert_always(always), the_allocator(alloc)
  589.     { 
  590.         init(); 
  591.         insert(first, last);
  592.     }
  593.     rb_tree (const_iterator first, const_iterator last, 
  594.              const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare()), bool always _RWSTD_DEFAULT_ARG(true),
  595.              const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
  596.           : node_count(0), key_compare(_RWSTD_COMP), 
  597.             insert_always(always), the_allocator(alloc)
  598.     { 
  599.         init(); 
  600.         insert(first, last);
  601.     }
  602.    
  603. #ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
  604.     rb_tree (const value_type* first, const value_type* last, 
  605.              const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare()))
  606.           : node_count(0), key_compare(_RWSTD_COMP), 
  607.             insert_always(true), the_allocator(Allocator())
  608.     { 
  609.         init(); 
  610.         insert(first, last);
  611.     }
  612.  
  613.     rb_tree (const value_type* first, const value_type* last, 
  614.              const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare()), bool always _RWSTD_DEFAULT_ARG(true))
  615.           : node_count(0), key_compare(_RWSTD_COMP), 
  616.             insert_always(always), the_allocator(Allocator())
  617.     { 
  618.         init(); 
  619.         insert(first, last);
  620.     }
  621.  
  622.     rb_tree (const_iterator first, const_iterator last, 
  623.              const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare()))
  624.           : node_count(0), key_compare(_RWSTD_COMP), 
  625.             insert_always(true), the_allocator(Allocator())
  626.     { 
  627.         init(); 
  628.         insert(first, last);
  629.     }
  630.  
  631.     rb_tree (const_iterator first, const_iterator last, 
  632.              const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare()), bool always _RWSTD_DEFAULT_ARG(true))
  633.           : node_count(0), key_compare(_RWSTD_COMP), 
  634.             insert_always(always), the_allocator(Allocator())
  635.     { 
  636.         init(); 
  637.         insert(first, last);
  638.     }
  639. #endif
  640.    
  641. #ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS    
  642.     rb_tree (const value_type* first, const value_type* last) 
  643.           : node_count(0), key_compare(Compare()), 
  644.             insert_always(true), the_allocator(Allocator())
  645.     { 
  646.         init(); 
  647.         insert(first, last);
  648.     }
  649.  
  650.     rb_tree (const_iterator first, const_iterator last) 
  651.           : node_count(0), key_compare(Compare()), 
  652.             insert_always(true), the_allocator(Allocator())
  653.     { 
  654.         init(); 
  655.         insert(first, last);
  656.     }
  657.  
  658. #endif
  659. #endif
  660.  
  661.     rb_tree (const rb_tree<Key,Value,KeyOfValue,Compare,Allocator>& x,
  662.              bool always = true)
  663.         : node_count(x.node_count), key_compare(x.key_compare),
  664.           insert_always(always)
  665.     { 
  666.         the_allocator = x.get_allocator();
  667.     {
  668. #ifdef _RWSTD_MULTI_THREAD
  669.         _RWSTDGuard guard(__stl_tree_mutex);
  670. #endif
  671. #ifndef __WIN16__
  672.             ++number_of_trees;
  673. #endif
  674.     }
  675.         buffer_size   = 1;
  676.     buffer_list   = 0;
  677.         free_list     = next_avail = last = 0;
  678.         header        = get_node();
  679.         buffer_size   = 
  680.      1 >  __RWSTD::__rw_allocation_size((value_type*)0,(size_type)0) ?
  681.      1 : __RWSTD::__rw_allocation_size((value_type*)0,(size_type)0);
  682. //max((size_type)1,__RWSTD::__rw_allocation_size((value_type*)0,(size_type)0));
  683.         color(header) = rb_red;
  684.         root()        = __copy(x.root(), header);
  685.         if (isNil(root()))
  686.         {
  687.             leftmost() = header; rightmost() = header;
  688.         }
  689.         else
  690.         {
  691.             leftmost() = minimum(root()); rightmost() = maximum(root());
  692.         }
  693.     }
  694.     ~rb_tree ()
  695.      {
  696.         erase(begin(), end());
  697.         put_node(header,false);
  698.         deallocate_buffers();
  699. #ifndef __WIN16__
  700. #ifdef _RWSTD_MULTI_THREAD
  701.     _RWSTDGuard guard(__stl_tree_mutex);
  702. #endif
  703.         if (--number_of_trees == 0)
  704.         {
  705.             node_alloc_type(the_allocator).deallocate(NIL,1);
  706.             NIL = 0;
  707.         }
  708. #endif
  709.     }
  710.  
  711.     rb_tree<Key, Value, KeyOfValue, Compare, Allocator>& 
  712.         operator= (const rb_tree<Key, Value, KeyOfValue, Compare, Allocator>& x);
  713.  
  714.     Compare     key_comp () const { return key_compare; }
  715.     allocator_type get_allocator() const
  716.     {
  717.         return the_allocator;
  718.     }
  719.  
  720.     iterator       begin ()       { return leftmost(); }
  721.     const_iterator begin () const { return leftmost(); }
  722.     iterator       end   ()       { return header;     }
  723.     const_iterator end   () const { return header;     }
  724.  
  725.     reverse_iterator rbegin ()
  726.     { 
  727.       reverse_iterator tmp(end()); return tmp;
  728.     }
  729.     const_reverse_iterator rbegin () const
  730.     { 
  731.       const_reverse_iterator tmp(end()); return tmp;
  732.     }
  733.     reverse_iterator rend ()
  734.     { 
  735.       reverse_iterator tmp(begin()); return tmp;
  736.     }
  737.     const_reverse_iterator rend () const
  738.     { 
  739.       const_reverse_iterator tmp(begin()); return tmp;
  740.     } 
  741.  
  742.     bool      empty    () const { return node_count == 0; }
  743.     size_type size     () const { return node_count;      }
  744.     size_type max_size () const
  745.     { 
  746.         return node_alloc_type(the_allocator).max_size(); 
  747.     }
  748.     void swap (rb_tree<Key, Value, KeyOfValue, Compare, Allocator>& t)
  749.     {
  750. #ifndef _RWSTD_NO_NAMESPACE
  751.         std::swap(the_allocator, t.the_allocator);
  752.         std::swap(buffer_list, t.buffer_list);
  753.         std::swap(free_list, t.free_list);
  754.         std::swap(next_avail, t.next_avail);
  755.         std::swap(last, t.last);
  756.         std::swap(header, t.header);
  757.         std::swap(node_count, t.node_count);
  758.         std::swap(insert_always, t.insert_always);
  759.         std::swap(key_compare, t.key_compare);
  760. #else
  761.         ::swap(the_allocator, t.the_allocator);
  762.         ::swap(buffer_list, t.buffer_list);
  763.         ::swap(free_list, t.free_list);
  764.         ::swap(next_avail, t.next_avail);
  765.         ::swap(last, t.last);
  766.         ::swap(header, t.header);
  767.         ::swap(node_count, t.node_count);
  768.         ::swap(insert_always, t.insert_always);
  769.         ::swap(key_compare, t.key_compare);
  770. #endif
  771.     }
  772.  
  773.     typedef  pair<iterator, bool> pair_iterator_bool;
  774.     //
  775.     // typedef done to get around compiler bug.
  776.     //
  777.  
  778. #ifndef _RWSTD_NO_RET_TEMPLATE
  779.     pair<iterator,bool> insert (const value_type& x);
  780. #else
  781.     pair_iterator_bool  insert (const value_type& x);
  782. #endif
  783.  
  784.     iterator  insert (iterator position, const value_type& x);
  785.  
  786. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  787. template<class Iterator>
  788.     void      insert (Iterator first, Iterator last);
  789. #else
  790.     void      insert (const_iterator first, const_iterator last);
  791.     void      insert (const value_type* first, const value_type* last);
  792. #endif
  793.  
  794.     iterator  erase  (iterator position);
  795.     size_type erase  (const key_type& x);
  796.     iterator  erase  (iterator first, iterator last);
  797.     void      erase  (const key_type* first, const key_type* last);
  798.  
  799.     iterator       find        (const key_type& x);
  800.     const_iterator find        (const key_type& x) const;
  801.     size_type      count       (const key_type& x) const;
  802.     iterator       lower_bound (const key_type& x);
  803.     const_iterator lower_bound (const key_type& x) const;
  804.     iterator       upper_bound (const key_type& x);
  805.     const_iterator upper_bound (const key_type& x) const;
  806.  
  807.     typedef  pair<iterator, iterator> pair_iterator_iterator; 
  808.     //
  809.     // typedef done to get around compiler bug.
  810.     //
  811. #ifndef _RWSTD_NO_RET_TEMPLATE
  812.     pair<iterator,iterator> equal_range (const key_type& x);
  813. #else
  814.     pair_iterator_iterator equal_range (const key_type& x);
  815. #endif
  816.  
  817.     typedef  pair<const_iterator, const_iterator> pair_citerator_citerator; 
  818. #ifndef _RWSTD_NO_RET_TEMPLATE
  819.     pair<const_iterator, const_iterator> equal_range (const key_type& x) const;
  820. #else
  821.     pair_citerator_citerator equal_range (const key_type& x) const;
  822. #endif
  823.     inline void rotate_left  (link_type x);
  824.     inline void rotate_right (link_type x);
  825.  
  826.     // Query and set the allocation size
  827.     size_type allocation_size() { return buffer_size; }
  828.     size_type allocation_size(size_type new_size) 
  829.     { 
  830.        size_type tmp = buffer_size; 
  831.        buffer_size = 1 > new_size ? 1 : new_size; //max((size_type)1,new_size);
  832.        return tmp;
  833.     }  
  834. };
  835.  
  836.  
  837. //
  838. // Inline functions
  839. //
  840.  
  841. template <class Key, class Value, class KeyOfValue, 
  842.           class Compare, class Allocator>
  843. inline bool operator== (const rb_tree<Key, Value, KeyOfValue, Compare, Allocator>& x, 
  844.                         const rb_tree<Key, Value, KeyOfValue, Compare, Allocator>& y)
  845. {
  846.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  847. }
  848.  
  849. template <class Key, class Value, class KeyOfValue, 
  850.           class Compare, class Allocator>
  851. inline bool operator< (const rb_tree<Key, Value, KeyOfValue, Compare, Allocator>& x, 
  852.                        const rb_tree<Key, Value, KeyOfValue, Compare, Allocator>& y)
  853. {
  854.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  855. }
  856.  
  857. template <class Key, class Value, class KeyOfValue, class Compare, class Allocator>
  858. inline void 
  859. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::rotate_left (link_type x)
  860. {
  861.     link_type y = right(x);
  862.     right(x) = left(y);
  863.     if (!isNil(left(y)))
  864.         parent(left(y)) = x;
  865.     parent(y) = parent(x);
  866.     if (x == root())
  867.         root() = y;
  868.     else if (x == left(parent(x)))
  869.         left(parent(x)) = y;
  870.     else
  871.         right(parent(x)) = y;
  872.     left(y) = x;
  873.     parent(x) = y;
  874. }
  875.  
  876.  
  877. template <class Key, class Value, class KeyOfValue, 
  878.           class Compare, class Allocator>
  879. inline void 
  880. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::rotate_right (link_type x)
  881. {
  882.     link_type y = left(x);
  883.     left(x) = right(y);
  884.     if (!isNil(right(y)))
  885.         parent(right(y)) = x;
  886.     parent(y) = parent(x);
  887.     if (x == root())
  888.         root() = y;
  889.     else if (x == right(parent(x)))
  890.         right(parent(x)) = y;
  891.     else
  892.         left(parent(x)) = y;
  893.     right(y) = x;
  894.     parent(x) = y;
  895. }
  896.  
  897. #ifndef _RWSTD_NO_NAMESPACE
  898. }
  899. #endif
  900.  
  901. #ifdef _RWSTD_NO_TEMPLATE_REPOSITORY
  902. #include <rw/tree.cc>
  903. #endif
  904.  
  905. #pragma option pop
  906. #endif /* __STD_TREE__ */
  907.